﻿namespace ZuoAlgorithms.Class006;

/// <summary>
/// 有序数组中找<=num的最右位置
/// </summary>
public class Code03_FindRight
{
    public void Main(string[] args)
    {
        int N = 100;
        int V = 1000;
        int testTime = 500000;
        for (int i = 0; i < testTime; i++)
        {
            Random rand = new Random();
            int n = (int)(rand.Next() * N);
            int[] arr = RandomArray(n, V);
            Array.Sort(arr);
            int num = (int)(rand.Next() * V);
            if (Right(arr, num) != FindRight(arr, num))
            {
                Console.WriteLine("出错了");
            }
        }
    }

    // 为了验证
    public int[] RandomArray(int n, int v)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            Random rand = new Random();
            arr[i] = (int)(rand.Next() * v) + 1;
        }
        return arr;
    }


    // 为了验证
    // 保证arr有序，才能用这个方法
    public int Right(int[] arr, int num)
    {
        for (int i = arr.Length - 1; i >= 0; i--)
        {
            if (arr[i] <= num)
            {
                return i;
            }
        }
        return -1;
    }

    // 保证arr有序，才能用这个方法
    // 有序数组中找<=num的最右位置
    public int FindRight(int[] arr, int num)
    {
        int left = 0;
        int right = arr.Length - 1;
        int m = 0;
        int res = -1;
        while (left <= right)
        {
            m = left + (right - left) / 2;
            if (arr[m] <= num)
            {
                res = m;
                left = m + 1;
            }
            else
            {
                right = m - 1;
            }
        }
        return res;

    }
}
